package com.ai.zuochengyun.phase01.class03;

/**
 * 是否是搜索二叉树
 */
public class Code20_IsSearchBinaryTree {

    public static void main(String[] args) {
        BinaryTreeNode head = new BinaryTreeNode(1);
        head.left = new BinaryTreeNode(2);
        head.right = new BinaryTreeNode(3);
        head.left.left = new BinaryTreeNode(4);
        head.left.right = new BinaryTreeNode(8);
        head.right.left = new BinaryTreeNode(5);
        head.right.right = new BinaryTreeNode(6);

        boolean isSBT = isSearchBinaryTree(head);
        System.out.println(isSBT);
    }

    public static boolean isSearchBinaryTree(BinaryTreeNode node) {
        if (node == null) {
            return true;
        }
        Info info = process(node);
        return info.isSBT;
    }

    public static Info process(BinaryTreeNode node) {
        if (node == null) {
            return null;
        }
        // 向左边要信息
        Info leftInfo = process(node.left);
        // 向右边要信息
        Info rightInfo = process(node.right);

        int min = node.value, max = node.value;
        // 收集左右树的最小值，然后得到较小的值作为min
        if (leftInfo != null) {
            min = Math.min(min, leftInfo.min);
        }
        if (rightInfo != null) {
            min = Math.min(min, rightInfo.min);
        }

        // 收集左右树的最大值，然后得到较大的值作为max
        if (leftInfo != null) {
            max = Math.max(max, leftInfo.max);
        }
        if (rightInfo != null) {
            max = Math.max(max, rightInfo.max);
        }

        boolean isSBT = true;
        if (leftInfo != null) {
            if (!leftInfo.isSBT) {
                isSBT = false;
            }

            // 左树的最大值应该小于X的值才对
            if (leftInfo.max >= node.value) {
                isSBT = false;
            }
        }
        if (rightInfo != null) {
            if (!rightInfo.isSBT) {
                isSBT = false;
            }

            // 右树的最小值应该大于X的值才对
            if (rightInfo.min <= node.value) {
                isSBT = false;
            }
        }

        return new Info(isSBT, min, max);
    }

    private static class Info {
        public boolean isSBT;

        public int max;

        public int min;

        public Info(boolean isSBT, int min, int max) {
            this.isSBT = isSBT;
            this.min = min;
            this.max = max;
        }
    }
}
